Rock, Paper, Scissors or... People are Predictable

The NY Times created a Rock, Paper, Scissors bot. If you try it, chances are it'll win handily. No matter how hard you try, you're going to fall into patterns that the computer is going to be able to identify and then exploit. As the article notes, if you were capable of producing truly random throws, then on average you'd win about as much as you lose, but humans are really bad at acting truly randomly.

For example, people seriously underestimate the probability of streaks. Let's say I throw Rock/Paper/Scissors 100 times, trying to be random. What do you think is the likelihood that I (a person trying to be random) would throw 4 in a row at some point? How about 5 in a row?

I haven't conducted that study, but my guess is that in both cases, it would be very uncommon: maybe 10-25% of the people.

But how likely is it that a truly random computer throws a streak of 4? Well that's something we can calculate. And it turns out the odds are 92%. Even 5 in a row is likely to happen 56% of the time.



In [43]:

    
import numpy as np
from numpy.linalg import matrix_power
import matplotlib.pyplot as plt

%matplotlib inline

How to compute the probabilities

How do we compute the probability of 4 in a row in a stream of 100 throws? We'll model it as a random walk around 4 possible states. After each throw, the possibilities will be that...

No streak. The last throw is different from the one before
2 element streak. The last two throws (but not third) are the same
3 element streak. The last three throws (but not the fourth) are the same.
4 element streak somewhere. At some point we've seen 4 in a row.

Some things to note

After 1 throw, we obviously start in State 1.
If we ever reach state 4, we stay there forever.
The probability of moving from State 1 to State 2, or State 2 to State 3, or State 3 to State 4 is 1/3
The probability of moving from State 1,2,3 back to State 1 is 2/3.

Put that all together into a matrix of transition probabilities, where M[i,j] is the probability of going to state i given state j, and you get this...



In [49]:

    
def transition_matrix(streak_length):
    """ TM[i,j] = Prob[transitioning to streak length i from streak length j]"""
    tm = np.zeros((streak_length, streak_length))
    tm[0,0:streak_length-1] = 2/3.0
    tm[1:streak_length, 0:streak_length-1] = np.eye(streak_length-1) * 1/3.0
    tm[streak_length-1, streak_length-1] = 1.0
    return np.matrix(tm)

tm = transition_matrix(4); tm









    Out[49]:





matrix([[ 0.66666667,  0.66666667,  0.66666667,  0.        ],
        [ 0.33333333,  0.        ,  0.        ,  0.        ],
        [ 0.        ,  0.33333333,  0.        ,  0.        ],
        [ 0.        ,  0.        ,  0.33333333,  1.        ]])

Given the first bullet point, The vector of state probabilities after the first throw is simply [1,0,0,0]: 100% probability of being in state 1.

If we want the state probabilities after 2 throws, we multiply this vector by the transition matrix tm, like so...



In [46]:

    
starting_vec = np.matrix([1,0,0,0]).transpose()
tm * starting_vec









    Out[46]:





matrix([[ 0.66666667],
        [ 0.33333333],
        [ 0.        ],
        [ 0.        ]])

Then the probabilities for N throws is tm^N * [1,0,0,0]'



In [47]:

    
def prob_of_run(streak_length, num_throws):
    starting_vec = np.zeros((streak_length,1))
    starting_vec[0] = 1.0
    tm_n = matrix_power(transition_matrix(streak_length), num_throws - 1)
    return (tm_n * starting_vec)[streak_length-1, 0]

The probability of a streak of length 4 is just the last element of that vector.

Below you have the results for streaks of various lengths, and different throw counts.



In [68]:

    
streak_lengths = range(2,10)
num_throws = [10, 25, 100, 500]
probs = [[prob_of_run(i, curr_throws) for i in streak_lengths] for curr_throws in num_throws]
line_fmts = ["go-","bo-","ro-", 'mo-']
for throws, prob, fmt in zip(num_throws, probs, line_fmts):
    plt.plot(streak_lengths, prob, fmt)
plt.ylabel("probability")
plt.xlabel("streak length")
plt.grid()
plt.legend(["%d throws" % i for i in num_throws])









    Out[68]:





<matplotlib.legend.Legend at 0x11083dad0>